#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

#define NULO 0
#define FALSE 0
#define TRUE 1

typedef struct Ruta{
	int ciudad_inicio;
	int ciudad_fin;
	int longitud;
} Ruta;

typedef struct Nodo{
	Nodo *proximo;
	Nodo *final_lista;
	Nodo *raiz;
	bool tiene_fabrica;
	int cantidad_de_elementos;
} Nodo;

void leerStdin();
vector<Ruta> construir_rutas(vector<Ruta> rutas, int fabricas, int clientes);
bool trd_order(Ruta r1, Ruta r2);
ostream& operator<<(ostream &os, vector<Ruta>);

int main(int argc, char *argv[]) {
	leerStdin();
	return 0;
}

void leerStdin() {
	while(1){
		/* Leer instancia */
		int fabricas(0);
		int clientes(0);
		int cantRutas(0);

		vector<Ruta> rutas(cantRutas);

		cin >> fabricas;

		if(fabricas == 0) break;
				
		cin >> clientes;
		cin >> cantRutas;

		for(int i = 0; i < cantRutas; i++) {
			Ruta* ruta = new Ruta;
			cin >> ruta->ciudad_inicio;
			cin >> ruta->ciudad_fin;
			cin >> ruta->longitud;
			rutas.push_back(*ruta);
		}				
		cout << construir_rutas(rutas, fabricas, clientes);
	}
}

vector<Ruta> construir_rutas(vector<Ruta> rutas, int fabricas, int clientes) {
	int primera_ciudad;
	int segunda_ciudad;
	
	vector<Ruta> resultado;
	
	Nodo *raiz1;
	Nodo *raiz2;
	Nodo *raizAux;
	Nodo *nodoAux;
	
	make_heap(rutas.begin(), rutas.end(), trd_order);
	Nodo* ciudades[fabricas + clientes];
	
	for(int i = 0; i < fabricas; i++) {
		Nodo *nodo_fabrica = new Nodo;
		nodo_fabrica->proximo = NULO;
		nodo_fabrica->final_lista = nodo_fabrica;
		nodo_fabrica->raiz = nodo_fabrica;
		nodo_fabrica->tiene_fabrica = TRUE;
		nodo_fabrica->cantidad_de_elementos = 1;
		
		ciudades[i] = nodo_fabrica;
	}

	for(int j = fabricas; j < (fabricas + clientes); j++) {
		Nodo *nodo_cliente = new Nodo;
		nodo_cliente->proximo = NULO;
		nodo_cliente->final_lista = nodo_cliente;
		nodo_cliente->raiz = nodo_cliente;
		nodo_cliente->tiene_fabrica = FALSE;
		nodo_cliente->cantidad_de_elementos = 1;
		
		ciudades[j] = nodo_cliente;
	}
	
	for (int k = 0; k < rutas.size(); k++) {
		//Levanto una ruta	
		primera_ciudad = rutas.front().ciudad_inicio;
		segunda_ciudad = rutas.front().ciudad_fin;
		
		primera_ciudad--;
		segunda_ciudad--;
		
		//Chequeo si no estan juntas o si ambas ya tienen una fábrica
		if((ciudades[primera_ciudad]->raiz != ciudades[segunda_ciudad]->raiz) && 
		(!(ciudades[primera_ciudad]->raiz->tiene_fabrica && 
		ciudades[segunda_ciudad]->raiz->tiene_fabrica))){
		
			raiz1 = ciudades[primera_ciudad]->raiz;
			raiz2 = ciudades[segunda_ciudad]->raiz;
			
			//Me fijo cual es la de longitud más corta	
			if(raiz1->cantidad_de_elementos < raiz2->cantidad_de_elementos) {
				raizAux = raiz1;
				raiz1 = raiz2;
				raiz2 = raizAux;
			}
			
			//Pongo la lista más pequeña atrás de la más grande y actualizo la raiz de la más grande
			(raiz1->final_lista)->proximo = raiz2;
			raiz1->final_lista = raiz2->final_lista;
			raiz1->tiene_fabrica = (raiz1->tiene_fabrica || raiz2->tiene_fabrica);
			raiz1->cantidad_de_elementos += raiz2->cantidad_de_elementos; 
			
			nodoAux = raiz2;
			
			//Actualizo los elementos de la lista más pequeña que estoy agregando
			for(int h = 0; h < raiz2->cantidad_de_elementos; h++) {
				nodoAux->raiz = raiz1;
				nodoAux = nodoAux->proximo;
			}
			
			resultado.push_back(rutas.front());
			pop_heap(rutas.begin(), rutas.end(), trd_order);
			rutas.pop_back();
		} else {
			pop_heap(rutas.begin(), rutas.end(), trd_order);
			rutas.pop_back();
		}
	}
	
	return resultado;
}

bool trd_order(Ruta r1, Ruta r2) {
	return (r1.longitud > r2.longitud);
}
	
ostream& operator<<(ostream &os, vector<Ruta> rutas) {
	int costo_total = 0;

	for (int a=0; a < rutas.size(); a++){

		costo_total = costo_total + rutas[a].longitud;

	}

	os << costo_total << " ";
	os << rutas.size() << " ";
	for(int b = 0; b < rutas.size(); b++){
		os << rutas[b].ciudad_inicio << " " << rutas[b].ciudad_fin << " "; 
	}
	os << endl;
}
